11158. Элегантно переставленная сумма

 

Задана последовательность из n целых чисел {a1, a2, …, an}. Необходимо найти такую перестановку, для которой сумма модулей разниц всех соседних элементов максимальна. Эту наибольшую сумму будем называть элегантной.

Рассмотрим, например, последовательность {4, 2, 1, 5}. Искомой является перестановка {2, 5, 1, 4}, искомая элегантная сумма равна |2 – 5| + |5 – 1| + |1 – 4| = 3 + 4 + 3 = 10. Для всех других перестановок значение элегантной суммы не больше 10.

 

Вход. Первая строка содержит количество тестов t (t < 100). Каждая следующая строка является отдельным тестом. Каждая входная строка начинается числом n (1 < n < 51), за которым следует последовательность из n неотрицательных чисел. Каждое число в последовательности не более 1000.

 

Выход. Для каждого теста вывести его номер и значение элегантной суммы.

 

Пример входа

3

4 4 2 1 5

4 1 1 1 1

2 10 1

 

Пример выхода

Case 1: 10

Case 2: 0

Case 3: 9

 

 

РЕШЕНИЕ

жадный алгоритм

 

Анализ алгоритма

Отсортируем числа входной последовательности a. Создадим новый массив v, в котором будем строить искомую перестановку. Изначально занесем в него минимальный и максимальный элементы последовательности a (и соответственно эти элементы удалим из а). Элегантную сумму будем подсчитывать в переменной s. Сначала положим s = | v[0] – v[1] |.

Пока массив a не пустой, жадным методом делаем наилучший выбор среди следующих четырех возможностей:

1. Наименьший элемент текущего массива а ставим в начало массива v.

2. Наименьший элемент текущего массива а ставим в конец массива v.

3. Наибольший элемент текущего массива а ставим в начало массива v.

4. Наибольший элемент текущего массива а ставим в конец массива v.

Для каждого случая пересчитываем новое значение s. Совершаем тот выбор, для которого новое значение s будет наибольшим.

Для каждого теста в качестве ответа выводим значение s.

 

Пример

Рассмотрим работу алгоритма на первом тесте.

Шаг 1. Отсортируем массив a: {1, 2, 4, 5}, изначально положим v = {1, 5}.

Возможный новый массив v

сумма модулей разниц

{2, 1, 5}

5

{1, 5, 2}

7

{4, 1, 5}

7

{1, 5, 4}

5

 

Шаг 2. a = {4}, v = {1, 5, 2}.

Возможный новый массив v

сумма модулей разниц

{1, 5, 2, 4}

9

{4, 1, 5, 2}

10

 

Искомая сумма равна 10, достигается она например на перестановке {4, 1, 5, 2}.

 

Реализация алгоритма

 

scanf("%d",&tests);

for(i = 1; i <= tests; i++)

{

 

Читаем входной массив а.

 

  scanf("%d",&n); a.clear(); v.clear();

  for(j = 0; j < n; j++) scanf("%d",&val), a.push_back(val);

 

Сортируем входной массив.

 

  sort(a.begin(),a.end());

 

Заносим минимальный и максимальный элементы последовательности a в массив v. Удаляем эти два элемента из массива а.

 

  v.push_back(a[0]); v.push_back(a[n-1]);

  iter = a.end(); iter--; a.erase(iter); a.erase(a.begin());

 

Положим изначально s = | v[0] – v[1] |.

 

  s = abs(v[1] - v[0]);

 

Пока массив а не пустой, рассматриваем 4 случая и делаем среди них оптимальный выбор жадным методом.

 

  while(!a.empty())

  {

    mx[0] = abs(v[0] - a[0]); mx[1] = abs(v[v.size()-1] - a[0]);

    mx[2] = abs(v[0] - a[a.size()-1]);

    mx[3] = abs(v[v.size()-1] - a[a.size()-1]);

    mmx = *max_element(mx,mx+4); iter = a.end(); iter--;

    if (mmx == mx[0]) v.insert(v.begin(),a[0]), a.erase(a.begin()); else

    if (mmx == mx[1]) v.push_back(a[0]), a.erase(a.begin()); else

    if (mmx == mx[2]) v.insert(v.begin(),a[a.size()-1]), a.erase(iter); else

                      v.push_back(a[a.size()-1]), a.erase(iter);

    s += mmx;

  }

 

Выводим ответ.

 

  printf("Case %d: %d\n",i,s);

}